Search Results

Documents authored by Walsh, Toby

Document
DOI: 10.4230/DagRep.7.6.109
Voting: Beyond Simple Majorities and Single-Winner Elections (Dagstuhl Seminar 17261)

Authors: Dorothea Baumeister, Piotr Faliszewski, Annick Laruelle, and Toby Walsh

Published in: Dagstuhl Reports, Volume 7, Issue 6 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17261 "Voting: Beyond simple majorities and single-winner elections". The seminar featured five survey talks, a series of classic scientific presentations, working group discussions, open problems sessions (with the first one used to establish working groups and the last one to present their results). The seminar was mostly focused on multiwinner elections (from discussions of their algorithmic properties to political-science considerations), but the topics of real-life voting experiments and strategic behavior received attention as well.
Cite as

Dorothea Baumeister, Piotr Faliszewski, Annick Laruelle, and Toby Walsh. Voting: Beyond Simple Majorities and Single-Winner Elections (Dagstuhl Seminar 17261). In Dagstuhl Reports, Volume 7, Issue 6, pp. 109-134, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{baumeister_et_al:DagRep.7.6.109,
  author =	{Baumeister, Dorothea and Faliszewski, Piotr and Laruelle, Annick and Walsh, Toby},
  title =	{{Voting: Beyond Simple Majorities and Single-Winner Elections (Dagstuhl Seminar 17261)}},
  pages =	{109--134},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{6},
  editor =	{Baumeister, Dorothea and Faliszewski, Piotr and Laruelle, Annick and Walsh, Toby},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.6.109},
  URN =		{urn:nbn:de:0030-drops-82882},
  doi =		{10.4230/DagRep.7.6.109},
  annote =	{Keywords: artificial intelligence, collective decision making, computational social choice, multi agent systems, preference aggregation, preference elicitation}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2012.188
Answer Set Solving with Lazy Nogood Generation

Authors: Christian Drescher and Toby Walsh

Published in: LIPIcs, Volume 17, Technical Communications of the 28th International Conference on Logic Programming (ICLP'12) (2012)

Abstract
Although Answer Set Programming (ASP) systems are highly optimised, their performance is sensitive to the size of the input and the inference it encodes. We address this deficiency by introducing a new extension to ASP solving. The idea is to integrate external propagators to represent parts of the encoding implicitly, rather than generating it a-priori. To match the state-of-the-art in conflict-driven solving, however, external propagators can make their inference explicit on demand. We demonstrate applicability in a novel Constraint Answer Set Programming system that can seamlessly integrate constraint propagation without sacrifficing the advantages of conflict-driven techniques. Experiments provide evidence for computational impact.
Cite as

Christian Drescher and Toby Walsh. Answer Set Solving with Lazy Nogood Generation. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 17, pp. 188-200, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{drescher_et_al:LIPIcs.ICLP.2012.188,
  author =	{Drescher, Christian and Walsh, Toby},
  title =	{{Answer Set Solving with Lazy Nogood Generation}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{188--200},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Dovier, Agostino and Santos Costa, V{\'\i}tor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2012.188},
  URN =		{urn:nbn:de:0030-drops-36216},
  doi =		{10.4230/LIPIcs.ICLP.2012.188},
  annote =	{Keywords: Conflict-Driven Nogood Learning, Constraint Answer Set Programming, Constraint Propagation, Lazy Nogood Generation}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2011.28
Modelling Grammar Constraints with Answer Set Programming

Authors: Christian Drescher and Toby Walsh

Published in: LIPIcs, Volume 11, Technical Communications of the 27th International Conference on Logic Programming (ICLP'11) (2011)

Abstract
Representing and solving constraint satisfaction problems is one of the challenges of artificial intelligence. In this paper, we present answer set programming (ASP) models for an important and very general class of constraints, including all constraints specified via grammars or automata that recognise some formal language. We argue that our techniques are effective and efficient, e.g., unit-propagation of an ASP solver can achieve domain consistency on the original constraint. Experiments demonstrate computational impact.
Cite as

Christian Drescher and Toby Walsh. Modelling Grammar Constraints with Answer Set Programming. In Technical Communications of the 27th International Conference on Logic Programming (ICLP'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 11, pp. 28-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{drescher_et_al:LIPIcs.ICLP.2011.28,
  author =	{Drescher, Christian and Walsh, Toby},
  title =	{{Modelling Grammar Constraints with Answer Set Programming}},
  booktitle =	{Technical Communications of the 27th International Conference on Logic Programming (ICLP'11)},
  pages =	{28--39},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-31-6},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{11},
  editor =	{Gallagher, John P. and Gelfond, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2011.28},
  URN =		{urn:nbn:de:0030-drops-31723},
  doi =		{10.4230/LIPIcs.ICLP.2011.28},
  annote =	{Keywords: answer set programming, grammar-, regular-, precedence constraint}
}
Document
DOI: 10.4230/DagSemProc.10101.4
Manipulability of Single Transferable Vote

Authors: Toby Walsh

Published in: Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010)

Abstract
For many voting rules, it is NP-hard to compute a successful manipulation. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. We study empirically the cost of manipulating the single transferable vote (STV) rule. This was one of the first rules shown to be NP-hard to manipulate. It also appears to be one of the harder rules to manipulate since it involves multiple rounds and since, unlike many other rules, it is NP-hard for a single agent to manipulate without weights on the votes or uncertainty about how the other agents have voted. In almost every election in our experiments, it was easy to compute how a single agent could manipulate the election or to prove that manipulation by a single agent was impossible. It remains an interesting open question if manipulation by a coalition of agents is hard to compute in practice.
Cite as

Toby Walsh. Manipulability of Single Transferable Vote. In Computational Foundations of Social Choice. Dagstuhl Seminar Proceedings, Volume 10101, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{walsh:DagSemProc.10101.4,
  author =	{Walsh, Toby},
  title =	{{Manipulability of Single Transferable Vote}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.4},
  URN =		{urn:nbn:de:0030-drops-25585},
  doi =		{10.4230/DagSemProc.10101.4},
  annote =	{Keywords: Computational social choice, manipulability, STV voting, NP-hardness}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact